package cn.bellychang.leetcode.question046;

import java.util.ArrayList;
import java.util.List;

/**
 * Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
 * <p>
 * Constraints:
 * All the integers of nums are unique.
 *
 * @author ChangLiang
 * @date 2021/2/9
 */
public class SolutionFail {

    // 搞了一下午的题目 得到的结论就是：不要在循环中递归

    public List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> allList = new ArrayList<>();

        if (nums.length == 1) {
            List<Integer> list = new ArrayList<>();
            list.add(nums[0]);
            allList.add(list);
            return allList;
        }

        for (int i = 0; i < nums.length; i++) {
            int[] subArray = getSubArray(nums, i);
            List<List<Integer>> subAllList = new ArrayList<>();
            doPermute(subArray, subAllList);
            for (List<Integer> integerList : subAllList) {
                integerList.add(nums[i]);
            }
            for (List<Integer> integerList : subAllList) {
                allList.add(integerList);
            }
        }
        return allList;
    }

    public List<List<Integer>> doPermute(int[] nums, List<List<Integer>> subAllList) {
        if (nums.length == 1) {
            List<Integer> list = new ArrayList<>();
            list.add(nums[0]);
            subAllList.add(list);
            return subAllList;
        }

        for (int i = 0; i < nums.length; i++) {
            int[] subArray = getSubArray(nums, i);
            subAllList = doPermute(subArray, subAllList);
            for (int j = i; j < subAllList.size(); j++) {
                subAllList.get(j).add(nums[i]);
            }
        }
        return subAllList;
    }

    private int[] getSubArray(int[] nums, int excludeIndex) {

        if (nums.length == 1) {
            return nums;
        }

        int[] result = new int[nums.length - 1];
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i != excludeIndex) {
                result[j++] = nums[i];
            }
        }
        return result;
    }

}
